package 归并排序;

public class Solution511 {
    public static void main(String[] args) {
        int[] nums = {7, 5, 6, 4};
        System.out.println(reversePairs(nums));
    }


    public static int reversePairs(int[] nums) {
        //先写递归
        return process(nums, 0, nums.length - 1);
    }

    public static int process(int[] nums, int l, int r) {
        //base case
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        //左排序
        int left = process(nums, l, mid);
        //右排序
        int right = process(nums, mid + 1, r);
        //merge
        int mer = merge(nums, l, mid, r);
        return left + right + mer;
    }

    public static int merge(int[] nums, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res=0;
        //边界条件
        while (p1 <= mid && p2 <= r) {
            if (nums[p1] <= nums[p2]) {
                help[i++] = nums[p1++];
            } else {
                res += mid - p1 + 1;
                help[i++] = nums[p2++];
            }
        }
        while (p1 <= mid) {
            help[i++] = nums[p1++];
        }

        while (p2 <= r) {
            help[i++] = nums[p2++];
        }
        for (int k = 0; k < help.length; k++) {
            nums[l + k] = help[k];
        }
        return res;
    }

}

